Пять замкнутых классов

Булева функция $f$ **сохраняет 0**, если $f(\vec{0}) = 0$. Булева функция $f$ **сохраняет 1**, если $f(\vec{1}) = 1$. Множество всех функций, сохраняющих 0, обозначается $T_0$. Множество всех функций, сохраняющих 1, обозначается $T_1$.

$T_0$ и $T_1$ — замкнутые классы.

Рассмотрим формулу над $T_0$ и построим по ней схему. Если любому элементу схемы подать $0$ на все входы, то на выходе у него будет $0$. Подадим $0$ на все входы схемы $\Rightarrow$ на выходе схемы будет $0$. Следовательно, функция, задаваемая схемой, принадлежит $T_0$. Для $T_1$ доказательство аналогично. $\square$

Функция $f(x_{1}, \dots, x_{k})$ **линейна**, если её полином Жегалкина — линейный.

$L$ — замкнутый класс.

Рассмотрим формулу над $L$ и построим по ней схему. Каждый элемент схемы вычисляет линейную функцию своих входов. Так как линейная функция от линейных функций переменных является линейной функцией этих переменных, то вся схема вычисляет линейную функцию. $\square$

Функция $f(x_{1}, \dots, x_{k})$ называется **самодвойственной**, если $f(\bar{x}_{1}, \dots, \bar{x}_{k}) = \overline{f(x_{1}, \dots, x_{k})}$

Класс самодвойственных функций $S$ — замкнутый.

Рассмотрим произвольную формулу над $S$ и построим по ней схему. Докажем, что при инвертировании всех входов схемы выход каждого элемента инвертируется. Используем индукцию по глубине (максимальной длине пути от входа до элемента). **База**: Входы элемента являются входами схемы. Так как они поменялись, а элемент вычисляет функцию из $S$, его выходной бит изменится. **Шаг**: Входы текущего элемента являются либо входами схемы, либо выходами предыдущих элементов. Все они инвертированы (по условию или предположению индукции). Поскольку элемент задает самодвойственную функцию, его выход также инвертируется. Следовательно, выходной бит всей схемы меняется на противоположный при инверсии входов, то есть схема реализует самодвойственную функцию. $\square$

Введем на битовых векторах равной длины **покомпонентный порядок**: $$(x_{1}, \dots, x_{k}) \le (y_{1}, \dots, y_{k}) \iff x_{1} \le y_{1}, \dots, x_{k} \le y_{k}$$ Диаграмма Хассе частично упорядоченного множества $(\{0, 1\}^{k}, \le)$ представляет собой **$k$-мерный куб**.

Функция $f(\vec{x})$ называется **монотонной**, если она сохраняет этот порядок: $$\forall{\vec{x}, \vec{y}}\mathpunct{:}~~ \vec{x} \le \vec{y} \Rightarrow f(\vec{x}) \le f(\vec{y})$$

Класс монотонных функций $M$ — замкнут.

Рассмотрим произвольную формулу над $M$ и построим по ней функциональную схему. Пусть на входы подан вектор $\vec{x}$. Изменим значения на некоторых входах с $0$ на $1$, получив вектор $\vec{y}$ (таким образом $\vec{x} \le \vec{y}$). Индукцией по глубине схемы (максимальной длине пути от входа до элемента) покажем, что ни у одного элемента выходной бит не изменится с $1$ на $0$. Так как каждый элемент схемы реализует монотонную функцию из $M$, то при неубывании значений на его входах, значение на выходе также не убывает. Следовательно, выходной бит всей схемы не уменьшится, то есть $f(\vec{x}) \le f(\vec{y})$, а значит схема вычисляет монотонную функцию. $\square$